import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/*
 *Description:
 *User:laoHu
 *Created with Intellij IDEA 2025
 *Data:2025.06.29
 *Time:21:44
 */
public class Main{
    //右旋
    //官方题解
    //1.增加额外数组
    public void rotate1(int[] nums, int k) {
        //创建临时数组
        int[] tem = Arrays.copyOf(nums,nums.length);
        int len = nums.length;
        k = k % len;
        for (int i = 0; i < len;i++) {
            tem[i] = nums[(len - k + i) % len];
        }
    }
    //环形交换
    public void rotate2(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int m = gcd(n,k);
        for (int start = 0; start < m; start++) {
            int current = start;
            int prev = nums[start];
            do{
                int next = (current + k) % n;
                int tem = prev;
                prev = nums[next];
                nums[next] = tem;
                current = next;
            }while(current != start);
        }
    }
    public int gcd(int x,int y)
    {
        return y > 0? gcd(y,x%y):x;
    }

    //自解
    public void reverse(int[] nums,int start,int end){
        while(start < end){
            int tem = nums[start];
            nums[start] = nums[end];
            nums[end] = tem;
            start++;
            end--;
        }
    }
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if(len == 1) return;
        else{
            int s = k % len;
            reverse(nums,0,len - s - 1);
            reverse(nums,len - s,len - 1);
            reverse(nums,0,len - 1);
        }
    }

//官方题解
//高斯求和：（n*n + n） /2
public int missingNumber4(int[] nums) {
    int len = nums.length;
    int total = (len*len + len)/ 2;
    int sum = 0;
    for(int i =0 ;i< len;i++){
        sum += nums[i];
    }
    return (total - sum);
}
//使用异或
public int missingNumber3(int[] nums) {
    int x = 0;
    for(int i = 0;i< nums.length;i++){
        x ^= nums[i];
    }
    for(int i = 0;i <= nums.length;i++){
        x^=i;
    }
    return x;
}
//哈希标记
    public int missingNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            set.add(nums[i]);//设置标记
        }
        //查找标记
        int missingNum = -1;
        int i =0;
        for(;i < nums.length;i++){
            if(!set.contains(i)){
                missingNum = i;
                break;
            }
        }
        if(i == nums.length) return i;
        else return missingNum;
    }
    //自己解题
        public static int missingNumber1(int[] nums) {
            Arrays.sort(nums);
            int i = 0;
            for(i = 0 ; i< nums.length;i++){
                if(nums[i] != i)  break;
            }
            if(i == nums.length) return i;
            else return (nums[i] - 1);
        }

    public static void main1(String[] args) {
        int[] nums = new int[4];
        int i = 0;
        for ( ; i < nums.length; i++) {
            nums[i] = i;
        }
        nums[i - 1] = i;
        int s = missingNumber1(nums);
        System.out.println(s);
    }
}